CF1166E The LCMs Must be Large
CF1166E The LCMs Must be
Large
思维好题，结论好题。
题意
一个长度为
的未知长度的序列，有
个限制，每个限制形如给定一个集合
，使集合内元素的
严格大于其补集元素的
。问是否存在这一序列。
思路
要注意我们是要尽可能使序列有解。
先给出结论：若所有集合两两间有交，则有解。否则一定无解。
首先有一个结论：若 ，那么
。
因为考虑 比
多的元素，只可能增加贡献而不可能减少贡献，所以上述结论显然。
然后我们回到题目：若一个限制的集合 与另一个限制的集合 不交，假设 (表示整个序列集合)，那么一定有 ,即有
。显然不符合要求。
然后证明结论的充分性。这里我们考虑一个构造的方法：假设所有元素初始都为1，我们将每个给定的集合内的元素都乘上一个互不相同的质数，那么如果集合两两相交，每个集合的就是整个序列的，并且每个集合的补集因为没有乘该集合的质数所以一定小。如果有两个集合不相交，因为两个集合的质数不同，所以一定会出现一个集合的大于另一个集合的情况，一定无解。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=1e4+10;
int m;
bitset<maxn> a[55],now;
inline void work(){
m=read();read();
for (int x,i=1;i<=m;i++) {
x=read();
while(x--)
a[i].set(read());
for (int j=1;j<i;j++) {
if ((a[i] & a[j]).none())
return (void)puts("impossible");
}
}
puts("possible");
}
}
signed main(){
star::work();
return 0;
}
|
